class Solution:
    def canCross(self, stones: list) -> bool:
        if stones[1] != 1:
            return False
        self.target = stones[-1]
        self.tar_set = {self.target, self.target - 1, self.target + 1}
        self.stones_set = set(stones)
        self.searched_set = set()
        return self.search(1, 1)

    def search(self, number: int, step: int) -> bool:
        mid_num = step + number
        if mid_num in self.tar_set:
            return True
        elif (number, step) in self.searched_set:
            return False
        else:
            if mid_num in self.stones_set and self.search(mid_num, step):
                return True
            if step > 1 and mid_num - 1 in self.stones_set and self.search(mid_num - 1, step - 1):
                return True
            if mid_num + 1 in self.stones_set and self.search(mid_num + 1, step + 1):
                return True
            self.searched_set.add((number, step))
            return False


a = Solution()
print(a.canCross([0, 1, 3, 5, 6, 8, 12, 17]))
print(a.canCross([0, 1, 2, 3, 4, 8, 9, 11]))
print(a.canCross([0, 1]))
